class Solution123 {
    public static void main(String[] args) {
        int[]arr = {2,1,4} ;
        maxProfit(arr)  ;
    }
    public static int maxProfit(int[] prices) {
         int n = prices.length ; 
         // 状态表示 : f[i][j] : 当第 i 天 结束时 , 完成了 j 次交易 , 处于买入状态
         int[][] f = new int[n][3] ; 
         // 状态表示 : g[i][j] : 当第 i 天 结束时 , 完成了 j 次 交易 , 处于 卖出状态  
         int[][] g = new int[n][3] ;
         // 初始化 
         f[0][0] = -prices[0] ; f[0][1] = f[0][2] = -0x3f3f3f3f ; 
         g[0][0] = g[0][1] = g[0][2] = -0x3f3f3f3f ; 
        
        for(int i=1 ; i < n ; i ++){
            for(int j=0 ; j < 3 ; j ++){
                // 状态转移方程 : max ( 前一天i-1天处于买入状态(第i天继续保持)  ,  前一天处于卖出状态, 第i天选择买入
                f[i][j] = Math.max(f[i-1][j] , g[i-1][j] - prices[i]) ; 
               // 状态转移方程 : 前一天处于卖出状态,完成了 j 次交易,  第 i天不买入, 继续保持
                g[i][j] = g[i-1][j] ;
                // 前一天处于买入状态, 同时 完成了 j-1次交易 , 选择第 i 天 卖出 , 卖出后就是完成了 j 次交易
                // 加个判断, 防止j-1越界 
                if(j >= 1) g[i][j] = Math.max(g[i][j] , f[i-1][j-1] + prices[i]) ; 
            }
        }

        // 最后返回 : 返回从第 i 天 ,  处于卖出状态的最大值里找
        int max = 0 ; 
        for(int i=1 ; i < n ; i ++){
          max = Math.max(g[i][2] , max)  ;
          max = Math.max(g[i][1] , max) ;  
        } 
        return max ; 
    }
}